package com.dex.youqu.utils;

import java.util.HashSet;
import java.util.List;
import java.util.Objects;
import java.util.Set;

/**
 * 算法工具类
 *
 * @author axin
 */
public class AlgorithmUtils {

    /**
     * 编辑距离算法（用于计算最相似的两组标签）
     * 原理：https://blog.csdn.net/DBC_121/article/details/104198838
     *
     * @param tagList1
     * @param tagList2
     * @return
     */
    public static int minDistance(List<String> tagList1, List<String> tagList2) {
        int n = tagList1.size();
        int m = tagList2.size();

        if (n * m == 0) {
            return n + m;
        }

        int[][] d = new int[n + 1][m + 1];
        for (int i = 0; i < n + 1; i++) {
            d[i][0] = i;
        }

        for (int j = 0; j < m + 1; j++) {
            d[0][j] = j;
        }

        for (int i = 1; i < n + 1; i++) {
            for (int j = 1; j < m + 1; j++) {
                int left = d[i - 1][j] + 1;
                int down = d[i][j - 1] + 1;
                int left_down = d[i - 1][j - 1];
                if (!Objects.equals(tagList1.get(i - 1), tagList2.get(j - 1))) {
                    left_down += 1;
                }
                d[i][j] = Math.min(left, Math.min(down, left_down));
            }
        }
        return d[n][m];
    }

    /**
     * 编辑距离算法（用于计算最相似的两个字符串）
     * 原理：https://blog.csdn.net/DBC_121/article/details/104198838
     *
     * @param word1
     * @param word2
     * @return
     */
    public static int minDistance(String word1, String word2) {
        int n = word1.length();
        int m = word2.length();

        if (n * m == 0) {
            return n + m;
        }

        int[][] d = new int[n + 1][m + 1];
        for (int i = 0; i < n + 1; i++) {
            d[i][0] = i;
        }

        for (int j = 0; j < m + 1; j++) {
            d[0][j] = j;
        }

        for (int i = 1; i < n + 1; i++) {
            for (int j = 1; j < m + 1; j++) {
                int left = d[i - 1][j] + 1;
                int down = d[i][j - 1] + 1;
                int left_down = d[i - 1][j - 1];
                if (word1.charAt(i - 1) != word2.charAt(j - 1)) {
                    left_down += 1;
                }
                d[i][j] = Math.min(left, Math.min(down, left_down));
            }
        }
        return d[n][m];
    }
    
    /**
     * 计算Jaccard相似度（用于标签匹配）
     * Jaccard相似度 = 交集大小 / 并集大小
     * 值越大表示越相似，范围为[0,1]
     *
     * @param tagList1 标签列表1
     * @param tagList2 标签列表2
     * @return 相似度，范围[0,1]，值越大表示越相似
     */
    public static double calculateJaccardSimilarity(List<String> tagList1, List<String> tagList2) {
        // 去重
        Set<String> set1 = new HashSet<>(tagList1);
        Set<String> set2 = new HashSet<>(tagList2);
        
        // 计算交集
        Set<String> intersection = new HashSet<>(set1);
        intersection.retainAll(set2);
        
        // 计算并集
        Set<String> union = new HashSet<>(set1);
        union.addAll(set2);
        
        // 防止除以0
        if (union.isEmpty()) {
            return 0.0;
        }
        
        // 计算Jaccard相似度
        return (double) intersection.size() / union.size();
    }
    
    /**
     * 计算标签匹配分数
     * 使用Jaccard相似度和共同标签数量的加权组合
     * 
     * @param tagList1 标签列表1
     * @param tagList2 标签列表2
     * @return 匹配分数，值越大表示越匹配
     */
    public static double calculateTagMatchScore(List<String> tagList1, List<String> tagList2) {
        // 去重
        Set<String> set1 = new HashSet<>(tagList1);
        Set<String> set2 = new HashSet<>(tagList2);
        
        // 计算交集（共同标签）
        Set<String> intersection = new HashSet<>(set1);
        intersection.retainAll(set2);
        
        // 计算Jaccard相似度
        double jaccardSimilarity = calculateJaccardSimilarity(tagList1, tagList2);
        
        // 共同标签数量
        int commonTagsCount = intersection.size();
        
        // 加权组合：0.7 * Jaccard相似度 + 0.3 * 共同标签数量
        // 这样既考虑了相对相似度，也考虑了绝对共同标签数
        return 0.7 * jaccardSimilarity + 0.3 * commonTagsCount;
    }
}
